package my.algo.sort;

/**
 * 排序算法
 * @author fengbo
 * @date 2018/7/23
 */
public class BasicSort {

    /**
     * 选择排序：找出数组中最小的那个元素，将它和数组的第一个元素交换位置，以此类推。
     */
    public static void selection(int[] a) {
        for (int i = 0; i < a.length; i++) {
			print(a);
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            exchange(a, i, min);
        }
    }

    /**
     * 插入排序：将一个数插入到一个已经有序的数组的适当位置。
     */
    public static void insertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
			if (a[i-1] < a[i]) {
				continue;
			}
			print(a);
            for (int j = i; j > 0 && a[j] < a[j-1]; j--) {
                exchange(a, j, j-1);
            }
        }
    }

    /**
     * 插入排序之希尔排序：使数组中任意间隔为h的元素都是有序的。
     */
    public static void shell(int[] a) {
        int n = a.length;
        int h = 1;
        while (h < n/3) {
            h = 3*h+1;
        }
        while (h >= 1) {
			// 根据分组进行的插入排序算法
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && a[j] < a[j-h]; j -= h) {
                    exchange(a, j, j-h);
                }
				print(a);
            }
            h = h/3;
			System.out.println();
        }
    }

	/** 
	 * 交换排序之冒泡排序：从后往前两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。
	 */
	public static void bubble(int[] a) {
		int n = a.length;
		for (int i = 0; i < n-1; i++) {
			print(a);
			boolean flag = false;
			for (int j = n-1; j > i;j--) {
				if (a[j-1] > a[j]) {
					exchange(a, j, j-1);
					flag = true;
				}
			}
			if (!flag) {
				return;
			}
		}	
	}

    /**
     * 二分法查询
     */
    private static int binarySearch(int val, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (hi >= lo) {
            // 为了防止(hi + lo)溢出
            int mid = lo + (hi - lo) / 2;
            if (val > a[mid]) {
                lo = mid + 1;
            } else if (val < a[mid]) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
	}

    private static void exchange(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void print(int[] a) {
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

}
